1. Field of the Invention
The present invention relates to the field of digital computation circuits. More specifically, the present invention relates to an incrementor based on a carry-skip technique and an optimal grouping of stages to selectively reduce total signal propagation delay.
2. Background Art Related to the Invention
Fundamental to the operations of any computer is the microprocessor. The microprocessor performs a number of arithmetical or logical "bitwise" calculations on its various inputs. One necessary arithmetic operation inherent in most advanced integrated circuit components, particularly microprocessors, is the ability to increment numbers in order to monitor the occurrence of events during each clock cycle. Throughout the development of integrated circuit components, a constant emphasis has been placed on increasing their speed of operation. Typically, this is accomplished by reducing signal propagation delays encountered by the integrated circuit component in completing a particular arithmetic operation.
For example, in their early development, processors usually employed an "i" bit ripple-carry incrementor operating independently or as a part of a half-adder. As shown in FIG. 1, the "i" bit ripple-carry incrementor 100 includes "i" identical cells 105a-105i ("i" being arbitrary) serially connected together. Each of these cells 105a-105i receives as input a serially transmitted ripple carry bit "C[x]" ("x".ltoreq."i") and a corresponding bit of a digital input operand A.sub.i ; namely, A[0] through A[i-1] respectively.
Each cell 105a-105i of the ripple-carry incrementor 100 comprises a XOR gate 110a-110i and an AND gate 115a-115i, which collectively enable each cell 105a-105i to perform two logical operations. Using the K.sup.th cell for illustrative purposes, its XOR gate 110k receives a ripple carry propagate "C[k-1]" bit from the K-1.sup.th cell (not shown) via a first input line 120 and an A[k-1] input bit via a second input line 125. Based on these inputs, the XOR gate 110k produces a real bit sum S[k-1] which is output from the incrementor 100 through a first output line 130. The K.sup.th cell also produces a ripple carry propagate "C[k]" bit via a second output line 135. The C[k] bit is a product of the C[k-1] bit logically AND'ed with the A[k-1] input bit. Thus, it is apparent that any ripple carry propagate output to a succeeding cell of the conventional ripple-carry incrementor 100 may be calculated by the following equation: EQU C[k]=(A[k-1].sup.* A[-2].sup.* A[k-3].sup.* . . . .sup.* A[k-x]).sup.* C[k-x],
where
(i) ".sup.* " represents a logical AND operator; and PA1 (ii) "k" represents the bit location of the cell from the least significant bit ("k" being arbitrary); and PA1 (iii) "x" represents the number of cells displaced from the k.sup.th cell ("x" being arbitrary and less than "k"). PA1 (i) T.sub.C : Time delay for a carry to propagate through each cell, where T.sub.c is approximately equal to one gate delay "T.sub.g "; and PA1 (ii) T.sub.S : Time delay for calculating S[i-1], approximately "T.sub.g ".
Although the conventional ripple-carry incrementor 100 is simple and requires little area and device count being the overall number of transistors required by the incrementor, its total signal propagation delay to calculate the real bit sum "S.sub.i " is unnecessarily large due to serial propagation of each ripple carry propagate. For example, for a 37-bit ripple-carry incrementor, the total signal propagation delay would be equal to the following: EQU Total Delay=(i-1).times.T.sub.C +T.sub.S =(37-1).times.T.sub.C +T.sub.S.apprxeq. 37T.sub.g
Thus, the ripple carry incrementor lies on one end of a speed/count continuum.
In certain situations, it is desirable to decrease the total signal propagation delay in order to increase the operational speed of the incrementor. This may be accomplished by sacrificing some area and device count. For example, incrementors using carry lookahead or Kogge-Stone techniques are specifically designed to reduce signal propagation delay. Unfortunately, these incrementors require significantly larger area and device count than conventional ripple carry incrementors and thus, lie on an end of the speed/area continuum opposite the ripple carry incrementor. Therefore, there exists a need for an incrementor experiencing less signal propagation delay than the ripple carry while further requiring lesser area and device count than the carry lookahead and Kogge-Stone incrementors. In other words, an incrementor which would lie on the speed/area continuum between the ripple carry and the carry lookahead and Kogge-Stone incrementors.
Hence, it would be desirable to provide an incrementor with a carry-skip technique and method for modifying the incrementor such that the total signal propagation delay is minimized for an incrementor of a specific bit width.